package algorithm.sort;

import java.util.Arrays;

/**
 * 堆排序：利用大顶堆来排序，1-先从上往下堆化；2-每一次取出堆的最大的元素，再堆化；
 */
public class HeapSortTest {
    public static void main(String[] args) {
        int[] arr = { 1, 12, 2, 13, 3, 14, 4, 15, 5, 16, 17, 17, 177, 18, 8, 8, 19 };
        sort(arr);
        System.out.println("result arr = " + Arrays.toString(arr));
    }

    public static void sort(int[] arr){
        // 建大顶堆，从上往下堆化
        buildHeap(arr, arr.length - 1);

        // 每次取出堆顶元素放在数组的后半段，n , n - 1, n - 2，以此类推
        int k = arr.length - 1;
        while (k > 0) {
            swap(arr, 0, k);
            k--;
            heapify(arr, 0, k);
        }
    }

    public static void buildHeap(int[] arr, int len){
        // 只有非叶子节点需要跟左右子节点比较所以只有n/2个非叶子节点
        for(int i = len/2; i >= 0; i--){
            heapify(arr, i, len);
        }
    }

    /**
     * 堆化：以i为顶点，向下堆化
     * @param arr
     * @param i 当前处理的元素的下标
     * @param len 堆的大小
     */
    public static void heapify(int[] arr, int i, int len){
        while(true){
            int max = i;
            // 2*i + 1代表的是左子节点
            if((2 * i + 1) <= len && arr[i] < arr[2 * i + 1]){
                max = 2 * i + 1;
            }
            // 2*i + 2代表的是右子节点
            if((2 * i + 2) <= len && arr[max] < arr[2 * i + 2]){
                max = 2 * i + 2;
            }
            if(max == i) break;
            swap(arr, i, max);
            i = max;
        }
    }

    public static void swap(int[] arr, int i , int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}
